{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个二叉树，找出其最小深度。\n",
    "\n",
    "最小深度是从根节点到最近叶子节点的最短路径上的节点数量。\n",
    "\n",
    "说明: 叶子节点是指没有子节点的节点。\n",
    "\n",
    "示例:\n",
    "```\n",
    "给定二叉树 [3,9,20,null,null,15,7],\n",
    "\n",
    "    3\n",
    "   / \\\n",
    "  9  20\n",
    "    /  \\\n",
    "   15   7\n",
    "返回它的最小深度  2.\n",
    "```\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "这道是简单题，我就直接写了，结果提交的时候`[1,2]` 我返回的是1 ，预期2，也就是说如果没有子节点，就要跳过他？\n",
    "\n",
    "并不是104题简单换一个min\n",
    "\n",
    "`[3,null,20,null,null,15,7]` 返回3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and root.right:\n",
    "            return self.minDepth(root.right) + 1\n",
    "        if not root.right and root.left:\n",
    "            return self.minDepth(root.left) + 1\n",
    "\n",
    "        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "这题是有特殊的返回条件的，就是叶子节点，如果他只有左，或者只有右，或者都有\n",
    "\n",
    "如果只是换一个min的话，`[1, 2]` 就只能返回1了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "##2020/8/21\n",
    "## 这是自己写的，如果只用一个函数，还是得好好想想\n",
    "class Solution:\n",
    "    def minDepth(self, root: TreeNode) -> int:\n",
    "\n",
    "        def helper(root, depth):\n",
    "            if not root:\n",
    "                return depth\n",
    "\n",
    "            if root.left and root.right:\n",
    "                return min(helper(root.left, depth+1), helper(root.right, depth+1))\n",
    "            elif root.left:\n",
    "                return helper(root.left, depth+1)\n",
    "            else:\n",
    "                return helper(root.right, depth+1)\n",
    "\n",
    "\n",
    "        return helper(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}